class Solution:
    def __init__(self):
        self.cache = {}

    def uniquePathsWithObstacles(self, obstacleGrid: List[List[int]]) -> int:
        m, n = len(obstacleGrid) - 1, len(obstacleGrid[0]) - 1
        self.obstacleGrid = obstacleGrid
        return self._unique_paths(m, n)

    def _unique_paths(self, m, n):
        if (m, n) in self.cache:
            return self.cache[(m, n)]
        if self.obstacleGrid[m][n] == 1:
            return 0
        if m == 0 and n == 0:
            return 1    
        if m == 0:
            return self._unique_paths(m, n-1)
        if n == 0:
            return self._unique_paths(m-1, n)
        res = self._unique_paths(m-1, n) + self._unique_paths(m, n-1)
        self.cache[(m, n)] = res
        return res
